#include <iostream>
#include <vector>
using namespace std;
void Merge(vector<int>& vc, int left, int mid, int right)
{
	vector<int> tmp;
	int i = left;
	int j = mid + 1;
	while (i <= mid && j <= right)
	{
		if (vc[i] < vc[j])
			tmp.push_back(vc[i++]);
		else
			tmp.push_back(vc[j++]);
	}

	while (i <= mid)
	{
		tmp.push_back(vc[i++]);
	}
	while (j <= right)
	{
		tmp.push_back(vc[j++]);
	}
	for (i = 0; i < tmp.size(); i++)
	{
		vc[left++] = tmp[i];
	}
}
void MergeSort(vector<int>& vc, int left, int right)
{
	if (left >= right)
		return;
	int mid = (left + right) >> 1;
	MergeSort(vc, left, mid);
	MergeSort(vc, mid + 1, right);
	Merge(vc, left, mid, right);
}
int main()
{
	vector<int> vc = { 3, 5, 2, 1, 7, 9, 8, 5, 10 };
	MergeSort(vc, 0, vc.size() - 1);
	for (auto e : vc)
	{
		cout << e << " ";
	}

	return 0;
}